import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
def get_root(s):
v = []
while not s == root[s]:
v.append(s)
s = root[s]
for i in v:
root[i] = s
return s
def unite(s, t):
rs, rt = get_root(s), get_root(t)
if not rs ^ rt:
return
if rank[s] == rank[t]:
rank[rs] += 1
if rank[s] >= rank[t]:
root[rt] = rs
size[rs] += size[rt]
else:
root[rs] = rt
size[rt] += size[rs]
return
def same(s, t):
return True if get_root(s) == get_root(t) else False
def get_size(s):
return size[get_root(s)]
n = int(input())
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
l = [i for i in range(n + 1)]
r = [i for i in range(n + 1)]
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
x, y = map(int, input().split())
x0, y0 = get_root(x), get_root(y)
lx, ly = l[x0], l[y0]
rx, ry = r[x0], r[y0]
G[lx].append(ry)
G[ry].append(lx)
unite(x, y)
r0 = get_root(x)
l[r0], r[r0] = rx, ly
for i in range(1, n + 1):
if len(G[i]) == 1:
s = i
break
ans = [s, G[s][0]]
for _ in range(n - 2):
for i in G[ans[-1]]:
if i ^ ans[-2]:
ans.append(i)
break
sys.stdout.write(" ".join(map(str, ans)))#include <bits/stdc++.h>
using namespace std;
const int c=200005;
int n;
vector<pair<int, int> > sz[c];
bool v[c];
priority_queue<pair<int, int> > q;
int main()
{
ios_base::sync_with_stdio(false);
cin >> n;
for (int i=1; i<n; i++) {
int a, b;
cin >> a >> b;
sz[a].push_back({b, i});
sz[b].push_back({a, i});
}
for (int i=2; i<=n; i++) {
sz[1].push_back({i, n});
}
q.push({0, 1});
while (q.size()>0) {
int a=q.top().second;
q.pop();
if (v[a]) continue;
cout << a << " ";
v[a]=true;
for (auto p:sz[a]) {
int b=p.first, x=p.second;
if (!v[b]) {
q.push({-x, b});
}
}
}
cout << "\n";
return 0;
}1553C - Penalty | 1474E - What Is It |
1335B - Construct the String | 1004B - Sonya and Exhibition |
1397A - Juggling Letters | 985C - Liebig's Barrels |
115A - Party | 746B - Decoding |
1424G - Years | 1663A - Who Tested |
1073B - Vasya and Books | 195B - After Training |
455A - Boredom | 1099A - Snowball |
1651D - Nearest Excluded Points | 599A - Patrick and Shopping |
237A - Free Cash | 1615B - And It's Non-Zero |
1619E - MEX and Increments | 34B - Sale |
1436A - Reorder | 1363C - Game On Leaves |
1373C - Pluses and Minuses | 1173B - Nauuo and Chess |
318B - Strings of Power | 1625A - Ancient Civilization |
864A - Fair Game | 1663B - Mike's Sequence |
448A - Rewards | 1622A - Construct a Rectangle |